702. Search in a Sorted Array of Unknown Size
Medium

This is an interactive problem.

You have a sorted array of unique elements and an unknown size. You do not have an access to the array but you can use the ArrayReader interface to access it. You can call ArrayReader.get(i) that:

  • returns the value at the ith index (0-indexed) of the secret array (i.e., secret[i]), or
  • returns 231 - 1 if the i is out of the boundary of the array.

You are also given an integer target.

Return the index k of the hidden array where secret[k] == target or return -1 otherwise.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: secret = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in secret and its index is 4.

Example 2:

Input: secret = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in secret so return -1.

 

Constraints:

  • 1 <= secret.length <= 104
  • -104 <= secret[i], target <= 104
  • secret is sorted in a strictly increasing order.
Accepted
48.2K
Submissions
69.5K
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.84 (45 votes)

Premium

Solution


Split into Two Subproblems

The array is sorted, i.e. one could try to fit into a logarithmic time complexity. That means two subproblems, and both should be done in a logarithmic time:

  • Define search limits, i.e. left and right boundaries for the search.

  • Perform binary search in the defined boundaries.

limits

Define Search Boundaries

This is a key subproblem here.

The idea is quite simple. Let's take two first indexes, 0 and 1, as left and right boundaries. If the target value is not among these zeroth and the first element, then it's outside the boundaries, on the right.

That means that the left boundary could moved to the right, and the right boundary should be extended. To keep logarithmic time complexity, let's extend it twice as far: right = right * 2.

limits

If the target now is less than the right element, we're done, the boundaries are set. If not, repeat these two steps till the boundaries are established:

  • Move the left boundary to the right: left = right.

  • Extend the right boundary: right = right * 2.

limits

Binary Search

Binary search is a textbook algorithm with a logarithmic time complexity. It's based on the idea to compare the target value to the middle element of the array.

  • If the target value is equal to the middle element - we're done.

  • If the target value is smaller - continue to search on the left.

  • If the target value is larger - continue to search on the right.

limits

Prerequisites: left and right shifts

To speed up, one could use here bitwise shifts:

  • Left shift: x << 1. The same as multiplying by 2: x * 2.

  • Right shift: x >> 1. The same as dividing by 2: x / 2.

Algorithm

Define boundaries:

  • Initiate left = 0 and right = 1.

  • While target is on the right to the right boundary: reader.get(right) < target:

    • Set left boundary equal to the right one: left = right.

    • Extend right boundary: right *= 2. To speed up, use right shift instead of multiplication: right <<= 1.

  • Now the target is between left and right boundaries.

Binary Search:

  • While left <= right:

    • Pick a pivot index in the middle: pivot = (left + right) / 2. To avoid overflow, use the form pivot = left + ((right - left) >> 1) instead of straightforward expression above.

    • Retrieve the element at this index: num = reader.get(pivot).

    • Compare middle element num to the target value.

      • If the middle element is the target num == target: return pivot.

      • If the target is not yet found:

        • If num > target, continue to search on the left right = pivot - 1.

        • Else continue to search on the right left = pivot + 1.

  • We're here because target is not found. Return -1.

Implementation

Complexity Analysis

  • Time complexity : O(logT)\mathcal{O}(\log T), where TT is an index of target value.

    There are two operations here: to define search boundaries and to perform binary search.

    Let's first find the number of steps k to setup the boundaries. On the first step, the boundaries are 20..20+12^0 .. 2^{0 + 1}, on the second step 21..21+12^1 .. 2^{1 + 1}, etc. When everything is done, the boundaries are 2k..2k+12^k .. 2^{k + 1} and 2k<T2k+12^k < T \le 2^{k + 1}. That means one needs k=logTk = \log T steps to setup the boundaries, that means O(logT)\mathcal{O}(\log T) time complexity.

    Now let's discuss the complexity of the binary search. There are 2k+12k=2k2^{k + 1} - 2^k = 2^k elements in the boundaries, i.e. 2logT=T2^{\log T} = T elements. As discussed, binary search has logarithmic complexity, that results in O(logT)\mathcal{O}(\log T) time complexity.

  • Space complexity : O(1)\mathcal{O}(1) since it's a constant space solution.

Report Article Issue

Comments: 19
just_hands13's avatar
Read More

as all the elements in the array are unique there can be max 2*10^5 elements ( according to constraints ). Also if we go out of bound of array we get 2147483647 in return
So we can simply apply binary search in start=0 and end=2 *10^5

25
Show 11 replies
Reply
Share
Report
ady_sn's avatar
Read More

We don't even need to find upper boundary in log(n) time. We can find the upper boundary in O(1) time

Explanation: Given all the elements in the Array are unique. If first value is n and we have all possible integers from n to target . 
		We will find the target at worst case  at (target - n) 
		Example: If First Element is -1 and target = 5 if the array had all elements between -1 and 5 i.e.,  
		[-1,0,1,2,3,4,5] Worst case 5 will be at (target - firstValue)

Solution: https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/discuss/595200/(SIMPLE)-Java-100-Faster-and-Memory-Less-than-100-of-Solution

11
Show 6 replies
Reply
Share
Report
dsalkamoses's avatar
Read More

nice article! however, left shift & right shift is wrongly represented in the definition.

5
Show 1 reply
Reply
Share
Report
gilbertotomasone's avatar
Read More

I use this to find the size of the array in the worst case:

int right = Math.abs(reader.get(0)) + Math.abs(target) + 1;

4
Reply
Share
Report
Yunxiang-Li's avatar
Read More

Hey guys, just a reminder, If you use C#, you should use ArrayReader's API interface as reader.get(index), not reader.Get(index) in comments above.

2
Show 1 reply
Reply
Share
Report
133c7's avatar
Read More

To speed up, one could use here bitwise shifts:

Interesting point. Could you provide any evidence/benchmark to back this up? Why not leave such a minute detail to the compilers (for Java, python, etc.)?

1
Show 1 reply
Reply
Share
Report
mrthepratik's avatar
Read More

nice writeup .

1
Reply
Share
Report
ritzsriv's avatar
Read More

ArrayReader API interface: int get(ArrayReader *, int index); not working for C implementation. Tried using get(reader, i) and it complains:

solution.c: In function ‘search’ Line 16: Char 12: warning: implicit declaration of function ‘get’; did you mean ‘gets’? [-Wimplicit-function-declaration] while (get(reader, r)< target){ ^~~ gets solution.c: In function ‘driver_helper’ Line 49: Char 5: warning: ignoring return value of ‘freopen’, declared with attribute warn_unused_result [-Wunused-result] int r = len-1; ^~~~~~~~~~~~~~ /tmp/ccAlSpZT.o:prog_joined.c:function search: error: undefined reference to 'get' /tmp/ccAlSpZT.o:prog_joined.c:function search: error: undefined reference to 'get' /tmp/ccAlSpZT.o:prog_joined.c:function search: error: undefined reference to 'get' collect2: error: ld returned 1 exit status

1
Show 1 reply
Reply
Share
Report
nazariyv's avatar
Read More

how about:

class Solution:
    def search(self, reader: 'ArrayReader', t: int) -> int:
        l, r = 0, 2 ** 31 - 1
        while l <= r:
            mid = l + (r - l) // 2
            val = reader.get(mid)
            if val == t: return mid
            elif val < t: l = mid + 1
            else: r = mid - 1
        return -1

is it wrong to set the upper limit on the size of the array? (i.e. 2 ** 31 - 1)?

1
Show 3 replies
Reply
Share
Report
fjiang91's avatar
Read More

See a better approach and the explanation in my post here:
https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/discuss/535941/Clean-binary-search-with-explanation-python-solution-no-need-doubling

No need to search for the upper bound like this here.

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium